/*
* Copyright (c) 2006 Michael Baczynski http://www.polygonal.de
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies.
* Michael Baczynski makes no representations about the suitability 
* of this software for any purpose.  
* It is provided "as is" without express or implied warranty.
*/
package com.atn.edamame
{
	import flash.display.*;
	import com.atn.edamame.*;
	public class RDC
	{
		public static var SUBDIVISION_THRESHOLD:int = 8;
		public static var CONTACT_THRESHOLD:Number = 0.01;
		
		public var collide:Function;
		
		public function RDC(collide:Function)
		{
			this.collide = collide;
		}
		
		private function bruteForce(group:Array):void
		{
			var k:uint = group.length;
			for (var i:uint = 0; i < k; i++)
			{
				for (var j:uint = i + 1; j < k; j++){
					collide(group[i], group[j]);
				}
			}
		}
		
		public function recursiveClustering(group:Array, axis1:int, axis2:int):void
		{
			if (axis1 == -1 || group.length < RDC.SUBDIVISION_THRESHOLD)
			{
				bruteForce(group);
			}
			else
			{
				var boundaries:Array = getOpenCloseBounds(group, axis1);
				boundaries.sortOn("pos", Array.NUMERIC);
				
				var newAxis1:int = axis2;
				var newAxis2:int = -1;
				
				var groupSubdivided:Boolean = false;
				
				var subgroup:Array = [], count:uint = 0;
				var k:uint = boundaries.length;
				for (var i:uint = 0; i < k; i++)
				{
					var b:Object = boundaries[i];
					if (b.type == "open")
					{
						count++;
						subgroup.push(b.obj);
					}
					else
					{
						count--;
						if (count == 0)
						{
							if (i != (k - 1))
							{
								groupSubdivided = true;
							}
							
							if (groupSubdivided)
							{
								if (axis1 == 0)
								{
									newAxis1 = 1;
								}
								else if (axis1 == 1)
								{
									newAxis1 = 0;
								}
							}
							
							recursiveClustering(subgroup, newAxis1, newAxis2);
							subgroup = [];
						}
					}
				}
			}
		}
		
		private function getOpenCloseBounds(group:Array, axis:uint):Array
		{
			var k:uint = group.length;
			
			var boundaries:Array = [], i:uint, o:EdamameObject;
			
			switch(axis)
			{
				case 0:
					for (i = 0; i < k; i++)
					{
						o = group[i];
						boundaries.push(new Entity("open",  o.x  + RDC.CONTACT_THRESHOLD, o));
						boundaries.push(new Entity("close", o.x + o.width - RDC.CONTACT_THRESHOLD, o));
					}
					break;
				case 1:
					for (i = 0; i < k; i++)
					{
						o = group[i];
						boundaries.push(new Entity("open",  o.y + RDC.CONTACT_THRESHOLD, o));
						boundaries.push(new Entity("close", o.y + o.height - RDC.CONTACT_THRESHOLD, o));
					}
			}
			return boundaries;
		}
	}
}

class Entity
{
	public var obj:Object;
	public var type:String;
	public var pos:Number;
	
	public function Entity(type:String, pos:Number, obj:*)
	{
		this.type = type;
		this.pos = pos;
		this.obj = obj;
	}
}